#include <bits/stdc++.h>

using namespace std;
class TrieNode
{
public:
    unordered_map<char, TrieNode *> children; // 使用指针存储子节点
    int cnt;
    TrieNode() : cnt(0) {}
};

class Trie
{
public:
    TrieNode *root;
    Trie()
    {
        root = new TrieNode();
    }

    void insert(string &s)
    {
        TrieNode *cur = root;
        for (char c : s)
        {
            if (!cur->children.count(c))
            {
                cur->children[c] = new TrieNode(); // 创建新节点
            }
            cur = cur->children[c];
        }
        cur->cnt++;
    }

    int find(string &s)
    {
        int _s = 0;
        TrieNode *cur = root;
        for (char c : s)
        {
            if (!cur->children.count(c))
                break;
            cur = cur->children[c];
            _s += cur->cnt;
        }
        return _s;
    }
};
